package leetcode.editor.cn;

//设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。 
//
// 示例： 
//
// 输入： arr = [1,3,5,7,2,4,6,8], k = 4
//输出： [1,2,3,4]
// 
//
// 提示： 
//
// 
// 0 <= len(arr) <= 100000 
// 0 <= k <= min(100000, len(arr)) 
// 
// Related Topics 堆 排序 分治算法 
// 👍 45 👎 0


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class SmallestKLcci {
    public static void main(String[] args) {
        Solution solution = new SmallestKLcci().new Solution();
        System.out.println(Arrays.toString(solution.smallestK(new int[]{1, 3, 5, 7, 2, 4, 6, 8}, 4)));


    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//    public int[] smallestK(int[] arr, int k) {
//        Arrays.sort(arr);
//        int[] arrays = new int[k];
//        for (int i = 0; i < k; i++) {
//            arrays[i] = arr[i];
//        }
//        return arrays;
//    }

        public int[] smallestK(int[] arr, int k) {
            int[] vec = new int[k];
            if (k == 0) { // 排除 0 的情况
                return vec;
            }
            PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
                // num1 - num2  正序  num2 - num1 倒序
                public int compare(Integer num1, Integer num2) {
                    return num2 - num1;
                }
            });
            for (int i = 0; i < k; ++i) {
                queue.offer(arr[i]);
            }
            for (int i = k; i < arr.length; ++i) {
                if (queue.peek() > arr[i]) {
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
//            for (int i = k-1; i >= 0; --i) {
//                vec[i] = queue.poll();
//            }
            for (int i = 0; i < k; ++i) {
                vec[i] = queue.poll();
            }
            return vec;
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}